The present invention relates to techniques for comparing one or more input strings to large sets of strings in a dictionary.
A variety of comparison techniques are used to compare strings to determine their similarities. For example, an input string may be compared to a set of known strings (such as words in a dictionary), and the results of these comparisons may be used to correct data-entry errors.
However, as the complexity of the set of known strings increases (for example, as the number of words in the dictionary grows), there is typically a commensurate increase in the number of comparison operations. For example, if the input string has n1 characters, an average string has n2 characters, and there are n3 strings to compare against the input string, the number of comparison operations is n1·n2·n3. As n3 increases, the number of comparisons becomes very large. This significantly increases the associated complexity and expense of the comparison operations, which often precludes the use of such comparison operations with large sets of strings.